Parallel computing applications such as Monte Carlo simulation and stochastic neural networks often use large numbers (e.g., hundreds or thousands) of random-number sequences. Often, a random-number sequence has a range of possible values that is convenient to implement, such as when the range of random numbers is a power of two (e.g., 2, 4, 8, . . . , 2n). For example, a circuit that generates eight random binary bits (i.e., eight bits were each bit has a value of either 0 or 1) may be used to generate a random number in a range from zero to 255, or 256 possible random numbers, which is a power of two (i.e., 28). This is accomplished by ordering the eight bits from a least significant bit to a most significant bit position, all of which are user-definable. Each bit position n is numbered, starting with one for the least significant bit position and incrementing to the most significant bit position. Next, a value is assigned to each bit position n (e.g., n=1, 2, . . . , 8 in the present example) that is equal to the value of the bit times 2n−1. Finally, the values of the bit positions are summed to determine the value of the bit sequence.
If each bit in a sequence is equally likely to be a 0 as it is to be a 1 then every possible outcome in the sequence (e.g., 0 to 255 for an eight-bit sequence) is equally likely to occur. If this condition exists then the sequence of n bits is said to be uniformly distributed over the set of integers {0, 1, . . . , 2n−1}. Such a sequence may also be said to be uniformly distributed over the set of integers zero to K, where the total number of bits K+1 (i.e., its range) is a power of two.
It is also possible to generate random sequences that are uniformly distributed over a range from zero to K, where K+1 is a prime number. However, as the prime number increases, so does the size of the circuit required to implement the random-number sequence generator as compared to that of a circuit that generates a random sequence uniformly distributed over a range that is a power of two.
Space-efficient digital filters constructed using stochastic computing cannot be limited to using random sequences having ranges that are powers of two. Prime number ranges are possible, but the large size of such random sequence generators would defeat the space-efficiency of the digital filter, which is one of its primary benefits.
Prior art methods of generating random number sequences over ranges that are not a power of two or a prime number fall into two categories (1) random sequence generators that use analog and digital circuitry and (2) all-digital random sequence generators that use multiple clock cycles to compute each random sequence. Analog components are complex and are not available in many digital integrated circuit processes. Requiring multiple clock cycles per random sequence decreases the performance of the generator. Therefore, there is a need for a method of generating a random sequence that is uniformly distributed over a range that is neither limited to being a power of two nor limited to being a prime number, does not include an analog component, and does not require multiple clock cycles per generated sequence (i.e., a method that generates a random sequence in one clock cycle).
U.S. Pat. No. 5,317,528, entitled “RANDOM NUMBER GENERATOR,” discloses a device for generating a random number that implements an improved linear congruential generation method. The linear congruential generation method is a method of generating a random number by selecting a prime number, determining one primitive root of the prime number, selecting a seed value, multiplying a seed value by the root of the prime number, and reducing the result modulo the prime number. The method used in U.S. Pat. No. 5,317,528 involves selecting a prime number, determining one primitive root of the prime number, selecting a seed value, multiplying a seed value or previously generated random number by the root of the prime number, adding the seed value, identifying the mth bit of the summation, and adding the mth bit to the summation to form a random number. The present invention does not use such a device or method. U.S. Pat. No. 5,317,528 is hereby incorporated by reference into the specification of the present invention.
U.S. Pat. No. 5,864,491, entitled “APPARATUS AND ASSOCIATED METHOD FOR GENERATING A PSEUDO RANDOM NUMBER,” discloses a device for and method of generating a pseudo random number by summing input sequences and filtering the same using an infinite impulse response (IIR) filter. The present invention does not use such a device or method. U.S. Pat. No. 5,864,491 is hereby incorporated by reference into the specification of the present invention.
U.S. Pat. No. 5,871,400, entitled “RANDOM NUMBER GENERATOR FOR ELECTRONIC APPLICATIONS,” discloses a device for and method of generating a random number by using a shift-register-based random-number generator configured to step as a primitive polynomial of degree k to generate random numbers. A second random number generator is used to store and retrieve the random numbers generated by the shift register. The present invention does not use such a device or method. U.S. Pat. No. 5,871,400 is hereby incorporated by reference into the specification of the present invention.
U.S. Pat. No. 6,141,668, entitled “PSEUDO RANDOM NUMBER GENERATING METHOD AND APPARATUS THEREFOR,” discloses a device for and method of generating a pseudo random number by generating an integer that satisfies a criteria involving prime numbers, forming a product of these prime numbers, dividing the product by each prime number, and forming a pseudo random number by adding products of the binary elements of the integer, the divided prime number products, and a modular reduced value of the integer. The present invention does not use such a device or method. U.S. Pat. No. 6,141,668 is hereby incorporated by reference into the specification of the present invention.
U.S. Pat. No. 6,480,870, entitled “RANDOM NUMBER GENERATOR USING LEHMER ALGORITHM,” discloses a device for and method of generating a random number by using a plurality of bit generators to produce a plurality of sum bits and a plurality of carry bits. The carry bits are converted to a three-bit number, which is then added to the sum bits to produce a random number. The present invention does not use such a device or method. U.S. Pat. No. 6,480,870 is hereby incorporated by reference into the specification of the present invention.
U.S. Pat. No. 7,099,366, entitled “PSEUDO-RANDOM NUMBER SEQUENCE OUTPUT UNIT, TRANSMITTER, RECEIVER, COMMUNICATION SYSTEM AND FILTER UNIT,” discloses a device for and method of generating a pseudo random number by calculating a recursive formula using a number, prescribed positive integers, a prescribed real impulse constant, and a prescribed non-zero real constant. The present invention does not use such a device or method. U.S. Pat. No. 7,099,366 is hereby incorporated by reference into the specification of the present invention.
U.S. Pat. Appl. Pub. No. US 2004/0005053 A1, entitled “CRYPTOGRAPHICAL PSEUDO-RANDOM NUMBER GENERATION APPARATUS AND PROGRAM,” discloses a device for and method of generating a pseudo random number by storing bit strings, taking the high order bits of the stored bits as an exponent, raising a value to the exponent, and using the result as the pseudo-random number. The present invention does not use such a device or method. U.S. Pat. Appl. Pub. No. US 2004/0005053 A1 is hereby incorporated by reference into the specification of the present invention.
U.S. Pat. No. 7,113,595, entitled “GENERATION OF A RANDOM NUMBER THAT IS NON-DIVISIBLE BY A SET OF PRIME NUMBERS,” discloses a device for and method of generating a random number by generating a number that is co-prime with a set of prime numbers without calculating the greatest common denominator of the numbers, and testing the generated number using the Carmichael function to determine if it is non-zero. If it is equal to zero then the generated number is treated as a random number. Otherwise, updating the generated number and repeating the above-identified steps. The present invention does not use such a device or method. U.S. Pat. No. 7,113,595 is hereby incorporated by reference into the specification of the present invention.
U.S. Pat. No. 7,047,262, entitled “ENTROPY ESTIMATION AND DECIMATION FOR IMPROVING THE RANDOMNESS OF TRUE RANDOM NUMBER GENERATION,” discloses a device for improving randomness in a random number generator using an entropy estimator to generate a signal indicative of the randomness of the output of a physical random number generator. The signal is processed by a decimator whose output represents a decimation of a true random number and a pseudo-random number. The present invention does not use such a device. U.S. Pat. No. 7,047,262 is hereby incorporated by reference into the specification of the present invention.